
//838.推多米诺
class Solution {
public:
    string pushDominoes(string dominoes) {
        //将区间可以分为始终[L,L],[R,R]这两种都是可以直接对数组进行修改的
        //[L,R]是不需要进行操作的;
        //[R,L]是需要对中间进行操作的

        // 如果数组最前面一个非.字符是L的话，为了组成[L,L]的形式，在原数组前面插上一个哨兵为L，结尾一样插入一个R
        string s="L"+dominoes+"R";
        int n=s.size();
        int prev=0;  //记录上一个字符位置
        for(int i=1;i<n;i++)
        {
            if(s[i]=='.') continue;
            if(s[prev]==s[i])
            {
                //是[L,L]或者[R,R]
                //从[prev,i]都是相同的L或者R
                fill(s.begin() + prev + 1, s.begin() + i, s[prev]);
            }

            else if(s[i]=='L')
            {
                //[R,L]的情况
                //一共有len=i-prev+1个元素
                int len=i-prev+1;
                //将其分为两半(prev,prev+len/2] [i-len/2+1,i)
                fill(s.begin() + prev + 1, s.begin() + prev + len / 2, s[prev]);
                fill(s.begin() + i - len / 2 + 1, s.begin() + i, s[i]);
            }
            prev = i;
        }
        return s.substr(1,n-2);
    }
};